package com.zh.note.huawei.twohundred.硬件产品销售方案;

import java.util.*;

/**
 * @Author: zhanghuan
 * @date: 2023/8/14 17:00
 * @description: create it
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // int sumTarget = sc.nextInt();
        // String inputStr = sc.nextLine();
        // int sumTarget = 500;
        // String inputStr = "[100, 200, 300, 500, 500]";
        int sumTarget = 100;
        String inputStr = "[100]";
        String replaceAll = inputStr.replaceAll(" ", "");
        String substring = replaceAll.substring(1).replace("]", "");
        int[] price = Arrays.stream(substring.split(",")).mapToInt(Integer::parseInt).toArray();
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(price, 0, path, res, 0, sumTarget);
        System.out.println(res);
    }

    //求组合数
    private static void dfs(int[] price, int startIndex, Deque<Integer> path, List<List<Integer>> res, int sum, int sumTarget) {
        if (sum > sumTarget) {
            return;
        }
        if (sum == sumTarget) {
            res.add(new ArrayList<>(path));
        }
        for (int i = startIndex; i < price.length; i++) {
            sum += price[i];
            path.addLast(price[i]);
            dfs(price, i, path, res, sum, sumTarget);
            path.removeLast();
            sum -= price[i];
        }
    }
}
